너비 우선 탐색(BFS)

인접한 노드를 먼저 탐색하는 방법

두 노드 사이의 최단 경로를 탐색할 때 활용하기 좋다.

Queue를 활용하여 탐색할 노드의 순서를 저장하고, 큐에 저장된 순서대로 탐색한다.

맹목적 탐색 방법의 하나로, 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다.

더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 탐색을 적용한다.

장점

출발 노드에서 목표 노드까지의 최단 길이 경로를 보장한다

단점

경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다

해가 존재하지 않는다면 유한 그래프의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다

구현 핵심

자료구조 Queue
방문 처리 배열 visited
방문한 노드를 저장하는 배열 ArrayList
Queue에 저장된 노드가 없을 때까지

BFS 알고리즘 탐색 과정

그래프 BFS

방문 체크를 한다! 해당 노드로 진입할 수 있는 경로가 1개 이상일 수 있기 때문에.

트리 BFS

방문 체크를 하지 않는다
왜? 루트 노드에서 시작하여 모든 간선이 부모 -> 자식으로 가고, 자식으로 진입할 수 있는 또 다른 부모(경로)가 없기 때문이다.